package com.linyaonan.leetcode.medium._117;

import java.util.LinkedList;

/**
 * 给定一个二叉树
 *
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * 初始状态下，所有 next 指针都被设置为 NULL。
 *
 *  
 *
 * 进阶：
 *
 * 你只能使用常量级额外空间。
 * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 与116思路类似，只不过117的树不再是完美二叉树，不能直接通过索引计算所在层数，所以需要单独进行记录
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        LinkedList<Node> list = new LinkedList<>();
        LinkedList<Integer> ceng = new LinkedList<>();

        list.addLast(root);
        ceng.addLast(1);

        addNext(list, ceng);

        return root;
    }

    private void addNext(LinkedList<Node> list, LinkedList<Integer> ceng) {
        Node first = null;
        Integer firstCeng = null;
        while (!list.isEmpty()) {
            Node top = list.removeFirst();
            Integer cengI = ceng.removeFirst();

            if (!cengI.equals(firstCeng)) {
                first = null;
            }

            if (first == null) {
                first = top;
                firstCeng = cengI;
            } else {
                first.next = top;
                first = first.next;
            }



            if (top.left != null) {
                list.addLast(top.left);
                ceng.addLast(cengI + 1);
            }
            if (top.right != null) {
                list.addLast(top.right);
                ceng.addLast(cengI + 1);
            }
        }
    }
}